Матч 318, Наибольший прямоугольник (BiggestRectangleEasy)

Дивизион 2, Уровень 1

У Джона есть n спичек, каждая из которых имеет длину 1. Он хочет составить из них прямоугольник наибольшей площади. Ломать спички нельзя. Джону не обязательно использовать все спички.

Класс: BiggestRectangleEasy

Метод: int findArea(int n)

Ограничения: 4 £ n £ 10000.

Вход. Количество спичек n, которое имеется в наличии у Джона.

Выход. Наибольшая площадь прямоугольника, который может составить Джон при помощи имеющихся у него спичек.

Пример входа

n

11

5

7254

Пример выхода

6

1

3288782

РЕШЕНИЕ

математика

Если одна из сторон прямоугольника равна x, то другую можно найти по формуле:

y = (n – 2*x) / 2

Площадь полученного прямоугольника равна S(x) = x * (n – 2*x) / 2. Она будет наибольшей в такой точке x, в которой S’(x) = 0. Имеем: S’(x) = (n – 4*x) / 2 = 0, x = n / 4. То есть искомым прямоугольником будет квадрат.

Если n не делится на 4, то выполняя целочисленные деления, получим правильный результат.

ПРОГРАММА

#include <stdio.h>

class BiggestRectangleEasy

{

public:

int findArea(int n)

{

int x = n / 4;

int y = (n - 2 * x) / 2;

return x * y;

}

};